pub fn c(n: usize, m: usize) -> Vec<Vec<usize>> {
    assert_ne!(n, 0);

    // C(n, m) = C(n - 1, m - 1) + C(n - 1, m)
    let mut result_vec: Vec<Vec<usize>> = Vec::new();
    if m == 0 {
        return vec![vec![]];
    }
    if m == 1 {
        for i in 0..n {
            result_vec.push(vec![i]);
        }
        return result_vec;
    }
    if n == m {
        let mut result: Vec<_> = Vec::new();
        for i in 0..n {
            result.push(i);
        }
        result_vec.push(result);
        return result_vec;
    }

    // C(n - 1, m - 1)
    let mut sub_result_vec1 = c(n - 1, m - 1);
    for sub_result in sub_result_vec1.iter_mut() {
        sub_result.push(n - 1);
    }

    // C(n - 1, m)
    let sub_result_vec2 = c(n - 1, m);

    // Combinds vec1 and vec2
    for sub_result in sub_result_vec2 {
        sub_result_vec1.push(sub_result);
    }

    sub_result_vec1
}

#[derive(PartialEq, Debug)]
pub enum RecordKind {
    Operational,
    Damaged,
    Unknown,
}

impl RecordKind {
    pub fn new(token: char) -> RecordKind {
        match token {
            '.' => RecordKind::Operational,
            '#' => RecordKind::Damaged,
            '?' => RecordKind::Unknown,
            _ => panic!("Unkown '{}'", token),
        }
    }
}

#[derive(PartialEq, Debug)]
pub struct Data {
    records: Vec<RecordKind>,
    damaged_counts: Vec<usize>,
    unkonw_positions: Vec<usize>,
}

impl Data {
    pub fn new(records: Vec<RecordKind>, damaged_counts: Vec<usize>, unkonw_positions: Vec<usize>) -> Self {
        Self { records, damaged_counts, unkonw_positions }
    }

    fn get_real_damaged_counts(&self) -> Vec<usize> {
        let mut res = Vec::new();
        let mut begin: usize = 0;

        while begin < self.records.len() {
            if self.records[begin] != RecordKind::Damaged {
                begin += 1;
                continue;
            }
            // Find next No damaged
            let mut end = begin + 1;
            loop {
                if end >= self.records.len() || self.records[end] != RecordKind::Damaged {
                    break;
                }
                end += 1;
            }
            // [begin, end) => all Damaged
            res.push( end - begin );
            begin = end + 1;
        }

        res
    }

    fn is_meet(&self) -> bool {
        let real_damaged_counts = self.get_real_damaged_counts();
        return real_damaged_counts == self.damaged_counts;
    }

    pub fn arrangement_size(&mut self) -> usize {
        let mut size = 0;

        let target_damaged_size: usize = self.damaged_counts.iter().sum();
        let exit_damaged_size: usize = self.records.iter()
                                                   .filter(|v| **v == RecordKind::Damaged)
                                                   .count();
        assert!(target_damaged_size >= exit_damaged_size);
        let need_damaged_size = target_damaged_size - exit_damaged_size;

        let exit_unkonw_size: usize = self.records.iter()
                                                  .filter(|v| **v == RecordKind::Unknown)
                                                  .count();

        let choises = c(exit_unkonw_size, need_damaged_size);

        for choise in choises {
            let indexs: Vec<usize> = choise.iter().map(|&c| self.unkonw_positions[c]).collect();
            for &i in indexs.iter() {
                self.records[i] = RecordKind::Damaged;
            }

            if self.is_meet() {
                size += 1;
            }

            for &i in indexs.iter() {
                self.records[i] = RecordKind::Unknown;
            }
        }

        size
    }
}

impl From<&str> for Data {
    fn from(value: &str) -> Self {
        let space_index = value.find(" ").unwrap();

        let records_str = &value[..space_index];
        let mut records: Vec<RecordKind> = Vec::new();
        let mut unkonw_positions: Vec<usize> = Vec::new();

        for (i, token) in records_str.chars().enumerate() {
            let kind = RecordKind::new(token);
            records.push(RecordKind::new(token));
            if kind == RecordKind::Unknown {
                unkonw_positions.push(i);
            }
        }

        let get_numbers = |s: &str| -> Vec<usize> {
            let mut numbers = Vec::new();
            for number_str in s.split(",") {
                numbers.push(number_str.parse().expect(s));
            }
            numbers
        };
        let damaged_counts_str = &value[space_index+1..];
        let damaged_counts = get_numbers(damaged_counts_str);

        Self { records, damaged_counts, unkonw_positions }
    }
}

